TIme complexity of binary search

How do we calculate the time complexity for binary search?

Check out the video below to get the gist, and then we'll walk through the process step-by-step after.

As Brynn said in the video, we can approximate the efficiency of binary search by answering this question: How many steps do we have to take in the worst-case scenario?

At each step, we check the middle element—and then we can rule out about half of the numbers (discarding everything to either the left or right). So if we start with n numbers, then after the first step we will have half that many, or \frac{n}{2} left that we still need to check.

Note: As Brynn showed, it won't always be exactly half the numbers that get discarded. If you have an even number of elements, you will have to check either the lower or higher of the middle two elements—and this means you'll rule out either half of the array, \frac{n}{2}, or one more than half the array, \frac{n}{2}+1. But when we calculate time complexity using big O notation, we tend to ignore such small details, because they have negligible impact on the efficiency. Usually, we are concerned with large input sizes—on the order of, say, 10^5. Imagine an array of size 10^5! It doesn’t really matter if each step rules out exactly half of the array, \frac{10^5}{2} or slightly more than half of the array, \frac{10^5}{2}+1. So to keep things simple here, we will ignore the +1.

QUIZ QUESTION::

The total number of integers in the array is n.

After each step, we reduce the number of elements remaining that we need to search.

How many elements will we have left after each step?

ANSWER CHOICES:

Here's what we're doing at each step:

• In the first step, we discard half of the numbers—that is, \frac{n}{2} numbers. So, the total number of remaining integers is also half, or \frac{n}{2}.

• In the second step, we discard half of the numbers that were left with us from the first step. We had \frac{n}{2} integers, so we discard half of these numbers and hence are left with \frac{n}{4} integers.

• Similarly, in the next step we again discard half of the numbers that were left in the last step. Thus, we are now left with \frac{n}{8} integers.

• We'll continue this process until, in the final step, we will have only one integer left. We will compare with this integer and check whether this is our target.

We start with n, which is the total number of indexes to search for our target number. And then, each time we check an index, we cut the search space in half.

Notice that this is the same as repeatedly multiplying by \frac{1}{2}.

QUIZ QUESTION::

Let's try a concrete example. Suppose we have n = 8, meaning that we have an array with eight elements. And suppose that the target number is not even in the array, so we must proceed with the maximum number of steps (i.e., the worst-case scenario).

In that case, what will we get after each step?

ANSWER CHOICES:

Thus, with a starting array size of n = 8, it will take at most three steps to find the target number.

So that's a specific example, but let's see if we can come up with a general equation that models this.

Now, what we need to know for calculating efficiency is the number of steps, s. We can solve for that algebraically.

In case you want to follow the math, here are the steps:

n * \frac{1}{2}^s = 1

Use the properties of negative exponents to rearrange the fraction:

n * 2^{-s} = 1

Divide both sides by {2^{-s}}

\frac{n * 2^{-s}}{2^{-s}} = \frac{1}{2^{-s}}

n = \frac{1}{2^{-s}}

Again use the properties of negative exponents to rearrange the fraction:

n = 2^s

Take the logarithm (base 2) of both side:

log_2(n) = log_2(2^s)

log_2(n) = s

The bottom line? The number of steps is equal to the logarithm of the input size:
s = log_2(n)

This is the number of steps it will require to find the target number in the worst case scenario. In big-O notation, we would say that the time complexity is O(log_2(n)).

If we look back at our comparison of computational complexities, we can see that this is extremely efficient:

In fact, this efficiency is the second best on the graph, with only constant time complexity, O(1) performing better!

Even as the input size grows very large, the number of steps required is still surprisingly small.

Going back to our guess-the-number game, you should now see why it's possible—using binary search—to correctly guess a number, out of 100. with only a handful of tries. If you like, go back and try inputs of 200 or even 1000. The algorithm will still perform quite well! (For an input of 1000, you might need slightly more than 7 tries.)